/**
 * 
 */
package solution.graph;

import java.util.HashSet;
import java.util.Set;

import lib.graph.Graph;
import lib.graph.Graph.E;
import lib.graph.Graph.V;
import lib.graph.GraphAdacentLink;

import org.junit.Test;

import data.Data;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class LongestPath {
	Graph g;

	Set<V> map = new HashSet<V>();

	public int getLongest() {
		int max = 0;
		for (V v : g.getV()) {
			int len = getLongest(v, 0);
			if (len > max) {
				max = len;
			}
		}
		return max;
	}

	public int getLongest(V v, int length) {
		if (v == null)
			return 0;

		if (map.contains(v))
			return 0;

		map.add(v);
		E[] es = g.getEs(v);
		int max = 0;
		for (E e : es) {
			int len = getLongest(e.to, length) + e.weight;
			if (len > max) {
				max = len;
			}
		}
		map.remove(v);
		return max;
	}

	@Test
	public void test() {
		String gStr = Data.getData("g1.txt");

		g = new GraphAdacentLink();
		g.load(gStr);

		System.out.print(getLongest());
	}
}
